{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from tqdm import tqdm\n",
    "from math import floor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "#######################################################################\n",
    "# Following are some utilities for tile coding from Rich.\n",
    "# To make each file self-contained, I copied them from\n",
    "# http://incompleteideas.net/tiles/tiles3.py-remove\n",
    "# with some naming convention changes\n",
    "#\n",
    "# Tile coding starts\n",
    "class IHT:\n",
    "    \"Structure to handle collisions\"\n",
    "    def __init__(self, size_val):\n",
    "        self.size = size_val\n",
    "        self.overfull_count = 0\n",
    "        self.dictionary = {}\n",
    "\n",
    "    def count(self):\n",
    "        return len(self.dictionary)\n",
    "\n",
    "    def full(self):\n",
    "        return len(self.dictionary) >= self.size\n",
    "\n",
    "    def get_index(self, obj, read_only=False):\n",
    "        d = self.dictionary\n",
    "        if obj in d:\n",
    "            return d[obj]\n",
    "        elif read_only:\n",
    "            return None\n",
    "        size = self.size\n",
    "        count = self.count()\n",
    "        if count >= size:\n",
    "            if self.overfull_count == 0: print('IHT full, starting to allow collisions')\n",
    "            self.overfull_count += 1\n",
    "            return hash(obj) % self.size\n",
    "        else:\n",
    "            d[obj] = count\n",
    "            return count\n",
    "\n",
    "def hash_coords(coordinates, m, read_only=False):\n",
    "    if isinstance(m, IHT): return m.get_index(tuple(coordinates), read_only)\n",
    "    if isinstance(m, int): return hash(tuple(coordinates)) % m\n",
    "    if m is None: return coordinates\n",
    "\n",
    "def tiles(iht_or_size, num_tilings, floats, ints=None, read_only=False):\n",
    "    \"\"\"returns num-tilings tile indices corresponding to the floats and ints\"\"\"\n",
    "    if ints is None:\n",
    "        ints = []\n",
    "    qfloats = [floor(f * num_tilings) for f in floats]\n",
    "    tiles = []\n",
    "    for tiling in range(num_tilings):\n",
    "        tilingX2 = tiling * 2\n",
    "        coords = [tiling]\n",
    "        b = tiling\n",
    "        for q in qfloats:\n",
    "            coords.append((q + b) // num_tilings)\n",
    "            b += tilingX2\n",
    "        coords.extend(ints)\n",
    "        tiles.append(hash_coords(coords, iht_or_size, read_only))\n",
    "    return tiles\n",
    "# Tile coding ends\n",
    "#######################################################################\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# all possible actions\n",
    "ACTION_REVERSE = -1\n",
    "ACTION_ZERO = 0\n",
    "ACTION_FORWARD = 1\n",
    "# order is important\n",
    "ACTIONS = [ACTION_REVERSE, ACTION_ZERO, ACTION_FORWARD]\n",
    "\n",
    "# bound for position and velocity\n",
    "POSITION_MIN = -1.2\n",
    "POSITION_MAX = 0.5\n",
    "VELOCITY_MIN = -0.07\n",
    "VELOCITY_MAX = 0.07\n",
    "\n",
    "# discount is always 1.0 in these experiments\n",
    "DISCOUNT = 1.0\n",
    "\n",
    "# use optimistic initial value, so it's ok to set epsilon to 0\n",
    "EPSILON = 0\n",
    "\n",
    "# maximum steps per episode\n",
    "STEP_LIMIT = 5000\n",
    "\n",
    "# take an @action at @position and @velocity\n",
    "# @return: new position, new velocity, reward (always -1)\n",
    "def step(position, velocity, action):\n",
    "    new_velocity = velocity + 0.001 * action - 0.0025 * np.cos(3 * position)\n",
    "    new_velocity = min(max(VELOCITY_MIN, new_velocity), VELOCITY_MAX)\n",
    "    new_position = position + new_velocity\n",
    "    new_position = min(max(POSITION_MIN, new_position), POSITION_MAX)\n",
    "    reward = -1.0\n",
    "    if new_position == POSITION_MIN:\n",
    "        new_velocity = 0.0\n",
    "    return new_position, new_velocity, reward\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# accumulating trace update rule\n",
    "# @trace: old trace (will be modified)\n",
    "# @activeTiles: current active tile indices\n",
    "# @lam: lambda\n",
    "# @return: new trace for convenience\n",
    "def accumulating_trace(trace, active_tiles, lam):\n",
    "    trace *= lam * DISCOUNT\n",
    "    trace[active_tiles] += 1\n",
    "    return trace"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# replacing trace update rule\n",
    "# @trace: old trace (will be modified)\n",
    "# @activeTiles: current active tile indices\n",
    "# @lam: lambda\n",
    "# @return: new trace for convenience\n",
    "def replacing_trace(trace, activeTiles, lam):\n",
    "    active = np.in1d(np.arange(len(trace)), activeTiles)\n",
    "    trace[active] = 1\n",
    "    trace[~active] *= lam * DISCOUNT\n",
    "    return trace\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# replacing trace update rule, 'clearing' means set all tiles corresponding to non-selected actions to 0\n",
    "# @trace: old trace (will be modified)\n",
    "# @activeTiles: current active tile indices\n",
    "# @lam: lambda\n",
    "# @clearingTiles: tiles to be cleared\n",
    "# @return: new trace for convenience\n",
    "def replacing_trace_with_clearing(trace, active_tiles, lam, clearing_tiles):\n",
    "    active = np.in1d(np.arange(len(trace)), active_tiles)\n",
    "    trace[~active] *= lam * DISCOUNT\n",
    "    trace[clearing_tiles] = 0\n",
    "    trace[active] = 1\n",
    "    return trace"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# dutch trace update rule\n",
    "# @trace: old trace (will be modified)\n",
    "# @activeTiles: current active tile indices\n",
    "# @lam: lambda\n",
    "# @alpha: step size for all tiles\n",
    "# @return: new trace for convenience\n",
    "def dutch_trace(trace, active_tiles, lam, alpha):\n",
    "    coef = 1 - alpha * DISCOUNT * lam * np.sum(trace[active_tiles])\n",
    "    trace *= DISCOUNT * lam\n",
    "    trace[active_tiles] += coef\n",
    "    return trace"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# wrapper class for Sarsa(lambda)\n",
    "class Sarsa:\n",
    "    # In this example I use the tiling software instead of implementing standard tiling by myself\n",
    "    # One important thing is that tiling is only a map from (state, action) to a series of indices\n",
    "    # It doesn't matter whether the indices have meaning, only if this map satisfy some property\n",
    "    # View the following webpage for more information\n",
    "    # http://incompleteideas.net/sutton/tiles/tiles3.html\n",
    "    # @maxSize: the maximum # of indices\n",
    "    def __init__(self, step_size, lam, trace_update=accumulating_trace, num_of_tilings=8, max_size=2048):\n",
    "        self.max_size = max_size\n",
    "        self.num_of_tilings = num_of_tilings\n",
    "        self.trace_update = trace_update\n",
    "        self.lam = lam\n",
    "\n",
    "        # divide step size equally to each tiling\n",
    "        self.step_size = step_size / num_of_tilings\n",
    "\n",
    "        self.hash_table = IHT(max_size)\n",
    "\n",
    "        # weight for each tile\n",
    "        self.weights = np.zeros(max_size)\n",
    "\n",
    "        # trace for each tile\n",
    "        self.trace = np.zeros(max_size)\n",
    "\n",
    "        # position and velocity needs scaling to satisfy the tile software\n",
    "        self.position_scale = self.num_of_tilings / (POSITION_MAX - POSITION_MIN)\n",
    "        self.velocity_scale = self.num_of_tilings / (VELOCITY_MAX - VELOCITY_MIN)\n",
    "\n",
    "    # get indices of active tiles for given state and action\n",
    "    def get_active_tiles(self, position, velocity, action):\n",
    "        # I think positionScale * (position - position_min) would be a good normalization.\n",
    "        # However positionScale * position_min is a constant, so it's ok to ignore it.\n",
    "        active_tiles = tiles(self.hash_table, self.num_of_tilings,\n",
    "                            [self.position_scale * position, self.velocity_scale * velocity],\n",
    "                            [action])\n",
    "        return active_tiles\n",
    "\n",
    "    # estimate the value of given state and action\n",
    "    def value(self, position, velocity, action):\n",
    "        if position == POSITION_MAX:\n",
    "            return 0.0\n",
    "        active_tiles = self.get_active_tiles(position, velocity, action)\n",
    "        return np.sum(self.weights[active_tiles])\n",
    "\n",
    "    # learn with given state, action and target\n",
    "    def learn(self, position, velocity, action, target):\n",
    "        active_tiles = self.get_active_tiles(position, velocity, action)\n",
    "        estimation = np.sum(self.weights[active_tiles])\n",
    "        delta = target - estimation\n",
    "        if self.trace_update == accumulating_trace or self.trace_update == replacing_trace:\n",
    "            self.trace_update(self.trace, active_tiles, self.lam)\n",
    "        elif self.trace_update == dutch_trace:\n",
    "            self.trace_update(self.trace, active_tiles, self.lam, self.step_size)\n",
    "        elif self.trace_update == replacing_trace_with_clearing:\n",
    "            clearing_tiles = []\n",
    "            for act in ACTIONS:\n",
    "                if act != action:\n",
    "                    clearing_tiles.extend(self.get_active_tiles(position, velocity, act))\n",
    "            self.trace_update(self.trace, active_tiles, self.lam, clearing_tiles)\n",
    "        else:\n",
    "            raise Exception('Unexpected Trace Type')\n",
    "        self.weights += self.step_size * delta * self.trace\n",
    "\n",
    "    # get # of steps to reach the goal under current state value function\n",
    "    def cost_to_go(self, position, velocity):\n",
    "        costs = []\n",
    "        for action in ACTIONS:\n",
    "            costs.append(self.value(position, velocity, action))\n",
    "        return -np.max(costs)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# get action at @position and @velocity based on epsilon greedy policy and @valueFunction\n",
    "def get_action(position, velocity, valueFunction):\n",
    "    if np.random.binomial(1, EPSILON) == 1:\n",
    "        return np.random.choice(ACTIONS)\n",
    "    values = []\n",
    "    for action in ACTIONS:\n",
    "        values.append(valueFunction.value(position, velocity, action))\n",
    "    return np.argmax(values) - 1\n",
    "\n",
    "# play Mountain Car for one episode based on given method @evaluator\n",
    "# @return: total steps in this episode\n",
    "def play(evaluator):\n",
    "    position = np.random.uniform(-0.6, -0.4)\n",
    "    velocity = 0.0\n",
    "    action = get_action(position, velocity, evaluator)\n",
    "    steps = 0\n",
    "    while True:\n",
    "        next_position, next_velocity, reward = step(position, velocity, action)\n",
    "        next_action = get_action(next_position, next_velocity, evaluator)\n",
    "        steps += 1\n",
    "        target = reward + DISCOUNT * evaluator.value(next_position, next_velocity, next_action)\n",
    "        evaluator.learn(position, velocity, action, target)\n",
    "        position = next_position\n",
    "        velocity = next_velocity\n",
    "        action = next_action\n",
    "        if next_position == POSITION_MAX:\n",
    "            break\n",
    "        if steps >= STEP_LIMIT:\n",
    "            print('Step Limit Exceeded!')\n",
    "            break\n",
    "    return steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      " 10%|█         | 3/30 [00:13<02:04,  4.62s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step Limit Exceeded!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 30/30 [02:15<00:00,  4.51s/it]\n",
      "100%|██████████| 30/30 [01:59<00:00,  3.98s/it]\n",
      "100%|██████████| 30/30 [01:50<00:00,  3.69s/it]\n",
      "100%|██████████| 30/30 [02:04<00:00,  4.17s/it]\n",
      "100%|██████████| 30/30 [01:58<00:00,  3.94s/it]\n",
      "100%|██████████| 30/30 [02:08<00:00,  4.28s/it]\n",
      "  0%|          | 0/30 [00:00<?, ?it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "  3%|▎         | 1/30 [00:52<25:35, 52.95s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step Limit Exceeded!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "  7%|▋         | 2/30 [00:59<11:57, 25.64s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      " 10%|█         | 3/30 [01:18<10:13, 22.72s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      " 13%|█▎        | 4/30 [01:31<08:04, 18.62s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      " 17%|█▋        | 5/30 [02:25<13:04, 31.37s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      " 20%|██        | 6/30 [03:47<19:33, 48.88s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      " 23%|██▎       | 7/30 [04:23<17:02, 44.44s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      " 27%|██▋       | 8/30 [04:31<12:01, 32.79s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      " 30%|███       | 9/30 [04:54<10:27, 29.86s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      " 33%|███▎      | 10/30 [05:17<09:13, 27.69s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      " 37%|███▋      | 11/30 [05:26<06:57, 21.97s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step Limit Exceeded!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      " 40%|████      | 12/30 [05:34<05:18, 17.72s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n",
      "Step Limit Exceeded!\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      " 43%|████▎     | 13/30 [05:59<05:39, 19.99s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step Limit Exceeded!\n"
     ]
    }
   ],
   "source": [
    "\n",
    "# figure 12.10, effect of the lambda and alpha on early performance of Sarsa(lambda)\n",
    "def figure_12_10():\n",
    "    runs = 30\n",
    "    episodes = 50\n",
    "    alphas = np.arange(1, 8) / 4.0\n",
    "    lams = [0.99, 0.95, 0.5, 0]\n",
    "\n",
    "    steps = np.zeros((len(lams), len(alphas), runs, episodes))\n",
    "    for lamInd, lam in enumerate(lams):\n",
    "        for alphaInd, alpha in enumerate(alphas):\n",
    "            for run in tqdm(range(runs)):\n",
    "                evaluator = Sarsa(alpha, lam, replacing_trace)\n",
    "                for ep in range(episodes):\n",
    "                    step = play(evaluator)\n",
    "                    steps[lamInd, alphaInd, run, ep] = step\n",
    "\n",
    "    # average over episodes\n",
    "    steps = np.mean(steps, axis=3)\n",
    "\n",
    "    # average over runs\n",
    "    steps = np.mean(steps, axis=2)\n",
    "\n",
    "    for lamInd, lam in enumerate(lams):\n",
    "        plt.plot(alphas, steps[lamInd, :], label='lambda = %s' % (str(lam)))\n",
    "    plt.xlabel('alpha * # of tilings (8)')\n",
    "    plt.ylabel('averaged steps per episode')\n",
    "    plt.ylim([180, 300])\n",
    "    plt.legend()\n",
    "\n",
    "\n",
    "figure_12_10()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 30/30 [00:27<00:00,  1.10it/s]\n",
      "  7%|▋         | 2/30 [00:01<00:26,  1.07it/s]\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[11], line 35\u001b[0m\n\u001b[1;32m     32\u001b[0m     plt\u001b[38;5;241m.\u001b[39mylim([\u001b[38;5;241m-\u001b[39m\u001b[38;5;241m550\u001b[39m, \u001b[38;5;241m-\u001b[39m\u001b[38;5;241m150\u001b[39m])\n\u001b[1;32m     33\u001b[0m     plt\u001b[38;5;241m.\u001b[39mlegend()\n\u001b[0;32m---> 35\u001b[0m \u001b[43mfigure_12_11\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\n",
      "Cell \u001b[0;32mIn[11], line 19\u001b[0m, in \u001b[0;36mfigure_12_11\u001b[0;34m()\u001b[0m\n\u001b[1;32m     17\u001b[0m                     steps \u001b[38;5;241m=\u001b[39m STEP_LIMIT\n\u001b[1;32m     18\u001b[0m                 \u001b[38;5;28;01melse\u001b[39;00m:\n\u001b[0;32m---> 19\u001b[0m                     steps \u001b[38;5;241m=\u001b[39m \u001b[43mplay\u001b[49m\u001b[43m(\u001b[49m\u001b[43mevaluator\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m     20\u001b[0m                 rewards[traceInd, alphaInd, run, ep] \u001b[38;5;241m=\u001b[39m \u001b[38;5;241m-\u001b[39msteps\n\u001b[1;32m     22\u001b[0m \u001b[38;5;66;03m# average over episodes\u001b[39;00m\n",
      "Cell \u001b[0;32mIn[9], line 19\u001b[0m, in \u001b[0;36mplay\u001b[0;34m(evaluator)\u001b[0m\n\u001b[1;32m     17\u001b[0m \u001b[38;5;28;01mwhile\u001b[39;00m \u001b[38;5;28;01mTrue\u001b[39;00m:\n\u001b[1;32m     18\u001b[0m     next_position, next_velocity, reward \u001b[38;5;241m=\u001b[39m step(position, velocity, action)\n\u001b[0;32m---> 19\u001b[0m     next_action \u001b[38;5;241m=\u001b[39m \u001b[43mget_action\u001b[49m\u001b[43m(\u001b[49m\u001b[43mnext_position\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mnext_velocity\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mevaluator\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m     20\u001b[0m     steps \u001b[38;5;241m+\u001b[39m\u001b[38;5;241m=\u001b[39m \u001b[38;5;241m1\u001b[39m\n\u001b[1;32m     21\u001b[0m     target \u001b[38;5;241m=\u001b[39m reward \u001b[38;5;241m+\u001b[39m DISCOUNT \u001b[38;5;241m*\u001b[39m evaluator\u001b[38;5;241m.\u001b[39mvalue(next_position, next_velocity, next_action)\n",
      "Cell \u001b[0;32mIn[9], line 8\u001b[0m, in \u001b[0;36mget_action\u001b[0;34m(position, velocity, valueFunction)\u001b[0m\n\u001b[1;32m      6\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m action \u001b[38;5;129;01min\u001b[39;00m ACTIONS:\n\u001b[1;32m      7\u001b[0m     values\u001b[38;5;241m.\u001b[39mappend(valueFunction\u001b[38;5;241m.\u001b[39mvalue(position, velocity, action))\n\u001b[0;32m----> 8\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[43mnp\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43margmax\u001b[49m\u001b[43m(\u001b[49m\u001b[43mvalues\u001b[49m\u001b[43m)\u001b[49m \u001b[38;5;241m-\u001b[39m \u001b[38;5;241m1\u001b[39m\n",
      "File \u001b[0;32m<__array_function__ internals>:200\u001b[0m, in \u001b[0;36margmax\u001b[0;34m(*args, **kwargs)\u001b[0m\n",
      "File \u001b[0;32m~/.local/lib/python3.8/site-packages/numpy/core/fromnumeric.py:1242\u001b[0m, in \u001b[0;36margmax\u001b[0;34m(a, axis, out, keepdims)\u001b[0m\n\u001b[1;32m   1155\u001b[0m \u001b[38;5;250m\u001b[39m\u001b[38;5;124;03m\"\"\"\u001b[39;00m\n\u001b[1;32m   1156\u001b[0m \u001b[38;5;124;03mReturns the indices of the maximum values along an axis.\u001b[39;00m\n\u001b[1;32m   1157\u001b[0m \n\u001b[0;32m   (...)\u001b[0m\n\u001b[1;32m   1239\u001b[0m \u001b[38;5;124;03m(2, 1, 4)\u001b[39;00m\n\u001b[1;32m   1240\u001b[0m \u001b[38;5;124;03m\"\"\"\u001b[39;00m\n\u001b[1;32m   1241\u001b[0m kwds \u001b[38;5;241m=\u001b[39m {\u001b[38;5;124m'\u001b[39m\u001b[38;5;124mkeepdims\u001b[39m\u001b[38;5;124m'\u001b[39m: keepdims} \u001b[38;5;28;01mif\u001b[39;00m keepdims \u001b[38;5;129;01mis\u001b[39;00m \u001b[38;5;129;01mnot\u001b[39;00m np\u001b[38;5;241m.\u001b[39m_NoValue \u001b[38;5;28;01melse\u001b[39;00m {}\n\u001b[0;32m-> 1242\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[43m_wrapfunc\u001b[49m\u001b[43m(\u001b[49m\u001b[43ma\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[38;5;124;43margmax\u001b[39;49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43maxis\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43maxis\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mout\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[43mout\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[43mkwds\u001b[49m\u001b[43m)\u001b[49m\n",
      "File \u001b[0;32m~/.local/lib/python3.8/site-packages/numpy/core/fromnumeric.py:54\u001b[0m, in \u001b[0;36m_wrapfunc\u001b[0;34m(obj, method, *args, **kwds)\u001b[0m\n\u001b[1;32m     52\u001b[0m bound \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mgetattr\u001b[39m(obj, method, \u001b[38;5;28;01mNone\u001b[39;00m)\n\u001b[1;32m     53\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m bound \u001b[38;5;129;01mis\u001b[39;00m \u001b[38;5;28;01mNone\u001b[39;00m:\n\u001b[0;32m---> 54\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[43m_wrapit\u001b[49m\u001b[43m(\u001b[49m\u001b[43mobj\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mmethod\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[43margs\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[43mkwds\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m     56\u001b[0m \u001b[38;5;28;01mtry\u001b[39;00m:\n\u001b[1;32m     57\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m bound(\u001b[38;5;241m*\u001b[39margs, \u001b[38;5;241m*\u001b[39m\u001b[38;5;241m*\u001b[39mkwds)\n",
      "File \u001b[0;32m~/.local/lib/python3.8/site-packages/numpy/core/fromnumeric.py:39\u001b[0m, in \u001b[0;36m_wrapit\u001b[0;34m(obj, method, *args, **kwds)\u001b[0m\n\u001b[1;32m     38\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21m_wrapit\u001b[39m(obj, method, \u001b[38;5;241m*\u001b[39margs, \u001b[38;5;241m*\u001b[39m\u001b[38;5;241m*\u001b[39mkwds):\n\u001b[0;32m---> 39\u001b[0m     \u001b[38;5;28;01mtry\u001b[39;00m:\n\u001b[1;32m     40\u001b[0m         wrap \u001b[38;5;241m=\u001b[39m obj\u001b[38;5;241m.\u001b[39m__array_wrap__\n\u001b[1;32m     41\u001b[0m     \u001b[38;5;28;01mexcept\u001b[39;00m \u001b[38;5;167;01mAttributeError\u001b[39;00m:\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "\n",
    "# figure 12.11, summary comparision of Sarsa(lambda) algorithms\n",
    "# I use 8 tilings rather than 10 tilings\n",
    "def figure_12_11():\n",
    "    traceTypes = [dutch_trace, replacing_trace, replacing_trace_with_clearing, accumulating_trace]\n",
    "    alphas = np.arange(0.2, 2.2, 0.2)\n",
    "    episodes = 20\n",
    "    runs = 30\n",
    "    lam = 0.9\n",
    "    rewards = np.zeros((len(traceTypes), len(alphas), runs, episodes))\n",
    "\n",
    "    for traceInd, trace in enumerate(traceTypes):\n",
    "        for alphaInd, alpha in enumerate(alphas):\n",
    "            for run in tqdm(range(runs)):\n",
    "                evaluator = Sarsa(alpha, lam, trace)\n",
    "                for ep in range(episodes):\n",
    "                    if trace == accumulating_trace and alpha > 0.6:\n",
    "                        steps = STEP_LIMIT\n",
    "                    else:\n",
    "                        steps = play(evaluator)\n",
    "                    rewards[traceInd, alphaInd, run, ep] = -steps\n",
    "\n",
    "    # average over episodes\n",
    "    rewards = np.mean(rewards, axis=3)\n",
    "\n",
    "    # average over runs\n",
    "    rewards = np.mean(rewards, axis=2)\n",
    "\n",
    "    for traceInd, trace in enumerate(traceTypes):\n",
    "        plt.plot(alphas, rewards[traceInd, :], label=trace.__name__)\n",
    "    plt.xlabel('alpha * # of tilings (8)')\n",
    "    plt.ylabel('averaged rewards pre episode')\n",
    "    plt.ylim([-550, -150])\n",
    "    plt.legend()\n",
    "\n",
    "figure_12_11()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
